package _19_面试题;

public class _17_10_面试题主要元素 {

    public static void main(String[] args) {

        _17_10_面试题主要元素 v = new _17_10_面试题主要元素();
        int[] ins = {1, 2, 5, 9, 5, 9, 5, 5, 5};
        System.out.println(v.majorityElement(ins));

    }

    public int majorityElement(int[] nums) {
        int num = 0;
        int count = 0;
        for (int j : nums) {
            if (count == 0) {
                num = j;
                count = 1;
            } else if (num == j) {
                count++;
            } else {
                count--;
            }
        }
        // 统计当前数字是否有超过一半
        int half = nums.length >> 1;
        count = 0;
        for (int i : nums) {
            if (i == num) {
                count++;
            }
            if (count > half) return num;
        }
        return -1;
    }

}
